package zuochengyun;

//最长无重复字符子串
public class MaxNORepeatSubString {

	public static void main(String[] args) {
		MaxNORepeatSubString object = new MaxNORepeatSubString();
		String str1 = "anmjkshuidsvgdshv";
		String str2 = "anfhmdzmdzshv";
		String str3 = "wefufvmshxshv";
		String str4 = "gfhzdnkvkzguk";
		System.out.println(object.maxUnique(str1));
		System.out.println(object.maxUnique(str2));
		System.out.println(object.maxUnique(str3));
		System.out.println(object.maxUnique(str4));
	}
	
	public int maxUnique(String str){
		if(str == null || str.equals("")){
			return 0;
		}
		char[] chars = str.toCharArray();
		//map的key表示某个字符，value为这个字符最近一次出现的位置
		int[] map = new int[256];
		//初识时置为-1
		
		for (int i = 0; i < map.length; i++) {
			map[i] = -1;
		}
		
		//最长无重复子串开始位置的前一个位置
		int pre = -1;
		int len = 0; //最小长度
		int cur = 0;  //当前长度
		for (int i = 0; i != chars.length; i++) {
			//map[chars[i]] 表示chars[i]最近一次出现的位置，假设在a位置
			//想要求以chars[i]结尾的最长无重复子串，a位置必然不能包含进来
			//根据pre的定义，pre+1表示必须以chars[i]结尾的情况下，无重复子串的开头
			//如果pre在a的左边，因为a位置不能包含进来，所以pre = a位置 
			//如果pre在a的右边，就是pre
			pre = Math.max(pre, map[chars[i]]);
			cur = i - pre;  //i - pre即为无重复的长度
			len = Math.max(len, cur);
			map[chars[i]] = i;
		}
		return len;
	}
}
